1. Field of the Invention
The present invention relates to signal processing, and, more specifically but not exclusively, to techniques for interleaving and de-interleaving.
2. Description of the Related Art
A multistage interconnection network (MIN) is a network constructed of a plurality of stages interconnected by wires or optical fibers, where each stage is constructed using one or more switching elements. Generally, a multistage interconnection network is defined by the number N of inputs to the network and the number M of outputs. For instance, an (N×M) multistage interconnection network is used for the interconnection of a set of N input terminals to a set of M output terminals. When the number N of input terminals of a multistage interconnection network is equal to the number M of output terminals, the multistage interconnection network may be designated as an (N×N) multistage interconnection network, having a size N. Currently, there are many different multistage interconnection networks known in the art such as Banyan networks, Clos networks, Belles networks, Delta networks, and Omega networks.
FIG. 1 shows a simplified block diagram of one implementation of a prior-art multistage interconnection network 100 known as an Omega network. In general, Omega networks are (N×N) multistage interconnection networks that are sized according to integer powers of two. Thus, Omega networks have sizes of N=2, 4, 8, 16, 32, 64, 128, etc. Further, the number L of stages in an Omega network is equal to log2(N) and the number of (2×2) switches per stage is equal to N/2.
Omega network 100 is an (8×8) network that receives eight input values at eight input terminals A[0:7] and maps the eight input values to eight output terminals B[0:7]. Each input value may be any suitable value such as a single bit, a plurality of bits, a sample, or a soft value (such as a Viterbi log-likelihood ratio (LLR) value) having a hard-decision bit and at least one confidence-value bit. The eight input values are mapped to the eight output terminals using log2(8)=3 configurable stages i, where i=1, 2, 3, each of which comprises 8/2=4 (2×2) switches.
Each stage i receives the eight input values from the previous stage, or from input terminals A[0:7] in the case of stage 1, via a fixed interconnection system (e.g., 102, 104, and 106) that implements a perfect shuffle on the eight input values. A perfect shuffle is a process equivalent to (i) dividing a deck of cards into two equal piles, and (ii) shuffling the two equal piles together in alternating fashion such that the cards in the first pile alternate with the cards from the second pile.
For example, stage 1 receives eight inputs values from input terminals A[0:7] via fixed interconnection system 102. Fixed interconnection system 102 performs a perfect shuffle on the eight input values by dividing the eight input values received at input terminals A[0:7] into a first set corresponding to input terminals A[0:3] and a second set corresponding to input terminals A[4:7]. The two sets are provided to stage 1 in alternating fashion such that the input values at input terminals A[0] and A[4] are provided to the upper and lower inputs of switch 108(0), respectively; the input values at input terminals A[1] and A[5] are provided to the upper and lower inputs of switch 108(1), respectively; the input values at input terminals A[2] and A[6] are provided to the upper and lower inputs of switch 108(2), respectively; and the input values at input terminals A[3] and A[7] are provided to the upper and lower inputs of switch 108(3), respectively. Similarly, fixed interconnection system 104 performs a perfect shuffle on the outputs of switches 108(0), 108(1), 108(2), and 108(3) and provides the shuffled outputs to switches 110(0), 110(1), 110(2), and 110(3) of stage 2, and fixed interconnection system 106 performs a perfect shuffle on the outputs of switches 110(0), 110(1), 110(2), and 110(3) and provides the shuffled outputs to switches 112(0), 112(1), 112(2), and 112(3) of stage 3.
In addition to receiving eight input values, each configurable stage i receives a four-bit control signal Ci[0:3] from control signal memory (e.g., ROM) 114, wherein each bit of the four-bit control signal configures a different one of the four 2×2 switches in the stage. Thus, switches 108(0), 108(1), 108(2), and 108(3) are configured based on the values of control bits C1[0], C1[1], C1[2], and C1[3], respectively, switches 110(0), 110(1), 110(2), and 110(3) are configured based on the values of control bits C2[0], C2[1], C2[2], and C2[3], respectively, and switches 112(0), 112(1), 112(2), and 112(3) are configured based on the values of control bits C3[0], C3[1], C3[2], and C3[3], respectively.
Setting a control bit to a value of one configures the corresponding switch as a crossed connection such that (i) the value received at the upper input is provided to the lower output and (ii) the value received at the lower input is provided to the upper output. Setting a control bit to a value of zero configures the corresponding switch as a straight pass-through connection such that (i) the value received at the upper input is provided to the upper output and (ii) the value received at the lower input is provided to the lower output.
In signal-processing applications, multistage interconnection networks, such as Omega network 100, are often used for routing purposes to connect processors on one end of the network to memory elements on the other end. However, multistage interconnection networks may also be used in signal-processing applications for other purposes, such as for permutating or interleaving a contiguous data stream.
Interleaving is used in many signal-processing systems to re-arrange a contiguous data stream in a non-contiguous manner. Often, interleaving is used to reduce the effects that burst errors in a transmission channel have on recovering data at a receiver. For example, in conventional hard-disk drive (HDD) systems, contiguous bits of a data stream may be interleaved before writing the data stream to a hard-disk platter. Upon retrieving the interleaved data stream, burst errors, which result in a plurality of consecutive interleaved bits of the data stream being in error, may occur. The read channel of the HDD system de-interleaves the bits of the interleaved data stream such that the errors are spread amongst the data stream. Spreading the errors increases the likelihood that an error-correction encoder can correct any errors present in the data stream.
Multistage interconnection networks are particularly useful in implementing local interleavers in local/global interleavers and local de-interleavers in local/global de-interleavers. Local/global interleavers, which are discussed in U.S. patent application Ser. No. 12/891,161 and U.S. patent application Ser. No. 12/835,989, perform both local interleaving on a local unit basis and global interleaving on a global unit basis, where (i) the unit basis refers to the number of values treated as a fixed unit for interleaving purposes and (ii) the global unit basis is larger than the local unit basis.
For example, in one implementation, a local/global interleaver has a local interleaver that receives sets of 96 values. The local interleaver interleaves the 96 in values in each set on a local unit basis, where the local unit basis (i.e., the number of values treated as a fixed local unit for local de-interleaving) is one value. Thus, the local interleaver interleaves 96 local units (i.e., 96 values) at the level of the individual value (i.e., value by value) to generate a set of 96 interleaved values.
After interleaving each set of 96 values, the local interleaver outputs one or more global units to a global interleaver. A global unit may be greater than the local set size (e.g., 96 values), equal to the local set size, or smaller than the local set size. For example, for each set of 96 values, the local interleaver may output one global unit having the 96 values or the local interleaver may output four global units in parallel, each having only 24 of the 96 values. The global interleaver then interleaves the global units at the level of the global unit (i.e., global unit by global unit) to generate interleaved global units. For example, the global interleaver may interleave multiple global units, where each global unit is itself either (i) a set of 96 interleaved values or (ii) a set of 24 interleaved values.
When implementing a multistage interconnection network, such as an Omega network, in a local/global interleaver or de-interleaver, the multistage interconnection network size should be selected appropriately for the number of inputs and the number of outputs to be interconnected. However, the number of inputs and the number of outputs to be interconnected might not correspond to a multistage interconnection network size. In such cases, a multistage interconnection network size may need to be selected that is capable of processing greater numbers of inputs and outputs than is actually needed for the particular signal-processing system. As a result, a number of input terminals and output terminals of the multistage interconnection network might not be used.
For example, suppose that an Omega network is used to implement a local interleaver in a local/global interleaver that interleaves 96 values. Since Omega networks are sized according to integer powers of two, there is no Omega network size corresponding to 96 inputs and 96 outputs. A (64×64) Omega network does not have enough input terminals to process all 96 values in a set at one time, and the smallest Omega network that can process 96 values at one time is a (128×128) Omega network. Using a (128×128) Omega network to process 96 values results in 32 input terminals and 32 output terminals of the Omega network being unused.
In performing an interleaving operation, the Omega network used to implement the local interleaver may output the 96 input values to any of the 128 output terminals depending on the configuration of the Omega network stages. Further, since different interleaving mappings may be used from one interleaving operation to the next, the locations of the used and unused output terminals may vary from one interleaving operation to the next. This variability may make it difficult to determine which output terminals of the Omega network should be provided to the global interleaver for global interleaving. Further, when the Omega network outputs multiple global units at a time (e.g., four 24-value global units for each set of 96 values output by the Omega network), this variability may make it difficult to ascertain the output terminals that correspond to each of the multiple global units. Thus, there is a need to (i) develop a method for ascertaining the locations of the used output terminals and route the used connections properly to the global interleaver or (ii) develop multistage interconnection networks in which the locations of the used output terminals and unused output terminals are fixed such that they do not vary from one interleaving operation to the next.
Referring again to (8×8) Omega network 100 of FIG. 1, for each interleaving mapping (i.e., particular routing of the eight inputs to the eight outputs), Omega network 100 stores twelve total control bits (i.e., one four-bit control signal for each of the three different stages). In some interleaving applications, the Omega network implements many different mappings. For example, suppose that Omega network 100 implements six different mappings. In such a case, control signal memory 114 stores six mappings×12 bits/mapping=72 total bits.
The number of control bits stored can be even greater for larger Omega networks. For example, suppose that a (128×128) Omega network is used to implement a local interleaver in the local/global interleaver described above. A (128×128) Omega network has log2(128)=7 stages, where each stage has 128/2=64 switches. The 7×64=448 total switches are configured based on 448 control bits for each interleaving mapping. Suppose also that the Omega network performs twelve different interleaving mappings. In this case, the control signal ROM stores 12×448=5,376 bits for the twelve different interleaving mappings.
It is preferable that the number of bits stored by the control signal ROM be reduced such that the size of the control signal ROM may be reduced. However, each of the bits stored by the control signal ROM is needed to configure a different switch in the Omega network. Simply reducing the number of control bits would result in one or more switches not receiving a control bit. Thus, there is a need to reduce the number of control signal bits that are stored by the control signal ROM, and yet still be able to provide a control bit to each of the switches in the Omega network.